


// 双向链表节点结构体
struct Node {
    int key;
    int value;
    Node* prev;
    Node* next;

    // 构造函数初始化节点
    Node(int k=0, int val=0) : key(k), value(val), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    int capacity;                       // 缓存容量
    unordered_map<int, Node*> cacheMap; // 哈希表：存储键到节点的映射
    Node* dummy;

    // 将指定节点删除
    void remove(Node* node) {
       node->prev->next=node->next;
       node->next->prev=node->prev;
    }

    // 添加新节点到双向链表的头部
    void addToHead(Node* node)
    {
        node->prev=dummy;
        node->next=dummy->next;
        node->prev->next=node;
        node->next->prev=node;
    }

    // 获取key对应的节点，同时移到链表头部
    Node* getNode(int key)
    {
        auto it=cacheMap.find(key);
        if(it==cacheMap.end())
        {
            return nullptr;
        }
        Node* node=it->second;
        remove(node);
        addToHead(node);
        return node;
    }

public:
    // 构造函数，初始化LRU缓存
    LRUCache(int capacity):capacity(capacity),dummy(new Node())
    {
        dummy->prev=dummy;
        dummy->next=dummy;
    }

    // 根据key获取value，若key不存在则返回-1
    int get(int key)
    {
        Node* node=getNode(key);
        return node?node->value:-1;
    }

    // 插入或更新缓存中key对应的value
    void put(int key, int value)
    {
        Node* node=getNode(key);
        if(node)
        {   //有这本书
            node->value=value;
            return;
        }
        node=new Node(key,value);
        cacheMap[key]=node;
        addToHead(node);
        if(cacheMap.size()>capacity)
        {
            //超出容量
            Node* tail=dummy->prev;
            cacheMap.erase(tail->key);
            remove(tail);
            delete tail;
        }
    }
};
